package chapter5_stack_and_linked;

import java.util.LinkedList;

/**
 * @author yuh
 * @date 2018/4/12 13:12
 * @description 无权图的最短路径的实际应用 无权图的最短的路径就是普通的广度优先遍历 谁的边最少谁就是最短路径
 *               一个节点往往和多个节点相连 广度优先遍历就是遍历和某一个节点相连的节点
 */
public class BFS {

    public static int getPerSquare(int num) {
        LinkedList<TwoTuple<Integer, Integer>> twoTuples = new LinkedList<>();
        twoTuples.addLast(new TwoTuple<>(num, 0));
        boolean[] visited = new boolean[num + 1];
        visited[num] = true;
        while (!twoTuples.isEmpty()) {
            TwoTuple<Integer, Integer> first = twoTuples.removeFirst();
            int n = first.a;
            int step = first.b;
            for (int i = 1; ; i++) {
                int a = n - i * i;
                if (a < 0) {
                    break;
                }
                if (a == 0) {
                    return step + 1;
                }
                //无权图的遍历 后遍历的点绝对不会比先遍历的点更近
                if (!visited[a]) {
                    twoTuples.addLast(new TwoTuple<>(a, step + 1));
                }
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        System.out.println(getPerSquare(2));
    }
}
